A detailed theoretical discussion of discrete cosine transforms in general is described in Reisch et al. U.S. Pat. No. 5,168,375 issued Dec. 1, 1992 and herein incorporated by reference in its entirety.
Color mapping is a process of converting an image from one color space to another. For example, well known standard sets of device independent color descriptors include CIELAB and CIEXYZ. Known device dependent systems may be characterized by color descriptors for each of three or more primary colors such as RGB, CMY etc. Color mapping can occur between any combination of device dependent and device independent color descriptors.
Various algorithms to map color are currently under development in the electronic imaging field. The performance factors which differentiate these color mapping algorithms include: quality or accuracy of the conversion; the computational time required to transform an image; and the amount of data storage required by the map. In general the algorithms may be implemented in a computer or in specialized hardware such as application specific integrated circuits (ASICS) or more general programmable digital signal processors (DSPs).
In an electronic digital still photographic system, a color image usually consists of three or more bands of quantized data. As a result, each pixel in the image is described by three bytes of data, one for each color band. Typically, the 256 discrete gradations provided by one byte are adequate for visual resolution. For purposes of the discussion herein, it will be assumed that the discretization process has not already introduced quantization artifacts. If the image detection or rendition mechanisms are linear with exposure or if the three color bands are independent but non-linear, color mapping may be implemented in a straightforward procedure using three one dimensional look-up tables and a 3.times.3 matrix. An electronic camera using a CCD or a CID for transforming the scene image through a series of electrical signals is such a linear detector.
A linear color map can be employed to effect a transformation from digitized electrical signals from a linear detector to a standard or device independent color space, for example, CIEXYZ units. However, the constraints of linearity or independence may not apply to the vast majority of color hard copy devices, i.e., printers. Accordingly, characterization of the printing or hard copy device is necessary in a characterization engine in order to obtain satisfactory tone and color in the hard copy.
Initially, at least one characterization of a hard copy output device is performed. The goal of characterizing the hard copy output device is to be able to compute a standard device independent color descriptor for any device dependent triplet of RGB data. While the CIELAB standard is a preferred device independent space, the same approach applies to any other choice of a device independent color descriptor.
In the interest of reducing quantization error, it is normally desirable to use three one dimensional (1D) look-up tables, such that, equal simultaneous digit increments in R, G and B result in corresponding equal L* increments and preserve a neutral balance (a*=b*=0), thereby linearizing the RGB space. The next step in the characterization process is to construct digital images which sample R, G, B space on a uniform three dimensional grid. A typical grid would equally sample R, G and B in eight steps resulting in 512 samples. These images are then printed and the printed colors are then measured in CIELAB units. The process thereby yields a uniform three dimensional (3D) grid of RGB values and their associated CIELAB values. In effect, the data may be viewed as consisting of three discretely sampled non-linear 3D functions--i.e., L* (R, G, B); a* (R, G, B); b* (R, G, B). All considerations of sampling theory apply. The calibration process enables one to predict by interpolation the CIELAB value that will result from printing any RGB triplet.
The primary function of an electronic printer is to consistently print any specified device independent triplet, whether it is a single pixel in an image or a patch of color. Mapping is the inverse of the above described characterization process, in that, given a L*a*b* triplet, it is desirable to obtain the correct RGB triplet necessary to supply the printer. In other words, given an image expressed in a device independent color space, mapping produces RGB outputs that are required to form the same image in the hard copy or medium.
There are a number of methods of performing this inversion. One that appears to be the fastest is to construct the uniform CIELAB grid, compute and construct corresponding RGB values in a grid and linearly interpolate the closest values from the CIELAB grid in the RGB grid to find the appropriate RGB triplet. The major difficulty in the construction of the uniform CIELAB grid is the proper handling of all the CIELAB triplets in the grid that are outside the gamut of the printer. These problems are typically handled by compromises and approximations, for example gamut tucking, which are known to those skilled in the art. Gamut tucking is a known process by which certain substitute independent color descriptors are used to specify device dependent descriptors which best match the desired color when the device is not capable of producing the desired color descriptors. The grid and its associated compromises make up the map which allows for consistent printing of an original image from data typically expressed in device independent color space values.
Interpolation represents an approximation. For example, in a typical arrangement for a given CIELAB coordinate, the nearest discrete coordinates in the grid are selected. The values are then transferred to the corresponding coordinates on the RGB map. Then a tri-linear (or multi-linear for more than three primary colors) interpolation is performed to ascertain the desired RGB value. FIGS. 1 and 2 illustrate an exemplary interpolation. In FIG. 1 the cube 10 represents a color space in CIELAB units in which the corners 12 of the cube 10 represent a limited number of color descriptors of the image. FIG. 2 represents a color map in RGB space of the cube 10 from FIG. 1. The solid 14 represents the color space defined by the corners of vertices 16. It can be seen that the cube 10 in FIG. 1 translates to a distorted solid 14 in FIG. 2 because the CIELAB and RGB systems describe colors in different ways. If a color in CIELAB space (FIG. 1) is defined by a discrete point corresponding to one of the vertices or corners 12 of the cube 10 then the color may be directly expressed by reference to the corresponding corner 16 of the solid 14 in RGB space (FIG. 2). If the point P occurs in the color space at a location other than at a discrete point or corner 12, the corresponding point P' in RGB must be found by linear interpolation.
The Table I below illustrates a simplified table of values of CIELAB and RGB units for the eight discrete points or corners 12 of the cube 10 and the corresponding discrete points 16 of the solid 14.
TABLE I ______________________________________ Lab RGB Coordinates Coordinates L* a* b* R G B ______________________________________ 0 0 0 0 0 0 1 0 0 1.5 0 0 0 1 0 0 0.75 0 1 1 0 1.5 0.75 0 0 0 1 0 0 1 1 0 1 2 0 1.5 0 1 1 0 1 1 1 1 1 1.5 1 1 ______________________________________
For simplicity, a one dimensional example is illustrated, i.e. keeping L* and a* on the grid point and only interpolating for the b* point. Thus, for an arbitrary point P having a set of CIELAB coordinates 1, 1, 0.5, the closest CIELAB coordinates are 1,1,0 and 1,1,1 (FIG. 1). The CIELAB coordinates are transferred to the RGB space as 1.5, 0.75, 0 and 1.5, 1, 1 respectively. By linear interpolation of P, the corresponding point P' 1.5, 0.865, 0.5 results (FIG. 2). A 3D case would require a more complex, but straightforward calculation involving as many as eight neighboring points.
It can be readily seen from FIGS. 1 and 2 that interpolation is an approximation because the only known points of correspondence between the two systems are the discrete points 12 and 16 of the corresponding solids 10 and 14. In other words, there is no guarantee that the system will result in a smooth transition from one system to the other.
In order to better assure accuracy and smoothness, it has been found necessary to select a minimum grid size of 16.sup.3. This creates a minimum of 4096 data points per color band which must be stored and manipulated. It is costly both in terms of processing time, storage requirements and expense to provide such capacity. Accordingly, a simplified technique is desirable.